class Solution {
public:
    void sortColors(vector<int>& nums) 
    {
        int n = nums.size();
        int i = 0, left = -1, right = n;
        while(i < right)
        {
            if(nums[i] == 0) swap(nums[++left],nums[i++]);
            else if(nums[i] == 1) ++i;
            else swap(nums[--right],nums[i]);
        }
    }
};

class Solution {
public:
    int getRan(vector<int>& nums, int l, int r)
    {
        int rd = rand();
        return nums[rd % (r - l + 1) + l];
    }

    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if(l == r) return nums[l];

        // partion
        int key = getRan(nums, l, r);
        int i = l, left = l - 1, right = r + 1;
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left], nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }

        //分情况讨论
        int c = r - right + 1, b = right - left - 1;
        if(c >= k) return qsort(nums, right, r, k);
        else if(c+b >= k) return key;
        else return qsort(nums, l, left, k - b -c);


    }

    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(0));
        return qsort(nums, 0, nums.size() - 1, k);    
    }
};


class Solution {
public:

    int getRand(vector<int>& nums, int l, int r)
    {
        int rd = rand();
        return nums[rd % (r - l + 1) + l];
    }

    void qsort(vector<int>& nums, int l, int r)
    {
        if(l >= r)  return;
        int key = getRand(nums, l, r);
        int i = l, left = l - 1, right = r + 1;
        while(i < right)
        {a
            if(nums[i] < key) swap(nums[++left], nums[i++]);
            else if(nums[i] == key) ++i;
            else swap(nums[--right], nums[i]);
        }

        //[l, left][left + 1, right - 1] [right, r]
        qsort(nums, l ,left);
        qsort(nums, right ,r);
    }

    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(0));
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }
};

class Solution {
    vector<int> tmp;
public:
    void mergeSort(vector<int>& nums, int left, int right)
    {
        //处理边界情况
        if(left >= right) 
            return;

        //划分区间归并
        int mid = (right+left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        //合并两个有序数组
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] >= nums[cur2]) 
                tmp[i++] = nums[cur2++];
            else 
                tmp[i++] = nums[cur1++];
        }
        //处理还没遍历完的数组
        while(cur1 <= mid) 
            tmp[i++] = nums[cur1++];
        while(cur2 <= right)
            tmp[i++] = nums[cur2++];
        //将tmp数组内容写回原数组
        for(int j = left; j <= right; j++)
        {
            nums[j] = tmp[j-left];
        }

    }

    vector<int> sortArray(vector<int>& nums) 
    {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
};




class Solution {
public:
    vector<int> tmp; // 辅助数组
    int mergeSort(vector<int>& nums, int left, int right)
    {
        //递归结束条件
        if(left >= right) return 0;

        //划分递归区间
        int mid = (right+left) >> 1;
        int ret = 0;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid+1, right);

        //归并排序
        
        int i = 0, cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmp[i++] = nums[cur2++];
            }
            else
            {
                ret += right-cur2 + 1;
                tmp[i++] = nums[cur1++];
            }
        } 
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];

        for(int j = left; j <= right; j++) nums[j] = tmp[j-left];

        return ret;
    }

    int reversePairs(vector<int>& record) 
    {
        int n = record.size();
        tmp.resize(n);
        return mergeSort(record, 0, n - 1);
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* cur1 = l1, *cur2 = l2;
        ListNode* newhead = new ListNode;
        ListNode* tail = newhead;
        int t = 0;
        while(cur1 || cur2 || t)
        {
            if(cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            if(cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            tail->next = new ListNode(t % 10);
            tail = tail->next;
            t/=10;
        }
        tail= newhead->next;
        delete newhead;
        return tail;
    }
};

class Solution {
public:
    int tmp[50010];
    int reversePairs(vector<int>& nums) 
    {
        return mergeSort(nums, 0, nums.size()-1);
    }

    int mergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return 0;
        int ret = 0;
        int mid = (right + left) >> 1;

        ret += mergeSort(nums,left, mid);
        ret += mergeSort(nums,mid+1, right);

        int cur1 = left, cur2 = mid + 1, i = left;
        while(cur1 <= mid)
        {
            while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0)
                cur2++;
            if(cur2 > right) 
                break;
            ret += right - cur2 + 1;
            cur1++;
        }
        
        cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur2] >= nums[cur1]) 
                tmp[i++] = nums[cur2++];
            else
                tmp[i++] = nums[cur1++];
        }
        while(cur1 <= mid) 
            tmp[i++] = nums[cur1++];
        while(cur2 <= right) 
            tmp[i++] = nums[cur2++];
        for(int j = left;j <= right; j++)
            nums[j] = tmp[j];
        return ret;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        //根据预处理前缀积和后缀积构建数组以达到空间换取时间。
        int n = nums.size();
        vector<int>f(n),g(n),ret(n);
        f[0] = 1,g[n-1] = 1;

        //预处理
        for(int i = 1; i < n;i++)
            f[i] = f[i-1] *nums[i-1];
        for(int i = n-2; i >= 0;i--)
            g[i] = g[i+1] *nums[i+1];

        for(int i = 0; i < n; i++)
        {
            ret[i] = f[i]*g[i];
        }
        return ret;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;
        ListNode* guard = new ListNode;
        guard->next = head;

        ListNode* prev = guard; 
        ListNode* cur = head;
        ListNode* next=nullptr,*nnext = nullptr;
        if(cur->next != nullptr)
        {
            next =cur->next;
            if(next)
            nnext = next->next;
        }
        while(cur && next)
        {
            prev->next = next;
            cur->next = nnext;
            next->next =cur;

            prev = cur;
            cur = nnext;
            if(cur != nullptr)
            {
                next = cur->next;
                if(next)
                nnext = next->next;
            }
        }
        cur = guard->next;
        delete guard;
        return cur;
    }
};

class Solution {
    int dx[4] = {0,0,-1,1};
    int dy[4] = {-1,1,0,0};
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) 
    {
        int n = isWater.size(), m = isWater[0].size();
        vector<vector<bool>> visi(n, vector<bool>(m));
        vector<vector<int>> ret(n, vector<int>(m));
        queue<pair<int, int>> q;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(isWater[i][j] == 1)
                {
                    ret[i][j] = 0;
                    q.push({i, j});
                    visi[i][j] = true;
                }

        while(q.size())
        {          
            auto [a, b] = q.front();
            q.pop();
            for(int i = 0; i < 4; i++)
            {
                int x = dx[i] + a, y = dy[i] + b;
                if(x >= 0 && x < n && y >= 0 && y < m && !visi[x][y])
                {
                    ret[x][y] = ret[a][b] + 1;
                    q.push({x, y});
                    visi[x][y] = true;
                }
            }
            
        }
        return ret;
    }
};



class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites) 
    {
        vector<int> ret(n);
        unordered_map<int, vector<int>> edges;
        vector<int> in(n);

        //构建图
        for(auto &e : prerequisites)
        {
            int a = e[0], b = e[1];
            edges[b].push_back(a);
            in[a]++;
        }

        //拓扑排序
        queue<int> q;

        for(int i = 0; i < n; i++)
            if(in[i] == 0)
                q.push(i);
        int index = 0;

        while(q.size())
        {
            int f = q.front();
            q.pop();
            ret[index++] = f;

            for(auto& e : edges[f])
            {
                in[e]--;
                if(in[e] == 0)
                    q.push(e);
            }
        }
        for(int i : in)
            if(i != 0)  return {};
        
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    bool check(TreeNode* p, TreeNode* q)
    {
        if(!q && !p) return true;
        if(!q || !p) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) 
    {
        return check(root, root);
    }
};